package com.jp.algorithm.sort;

public class FindKthLargest {

    public static int findKthLargest(int[] nums, int k) {
        find(nums,0,nums.length-1,k);
        return nums[k-1];
    }

    public static void find(int[] nums, int start, int end, int k) {
        if (end <= start) {
            return;
        }
        int l = start;
        int h = end;
        int tmp = nums[l];
        while (l < h) {
            while (l < h) {
                if (nums[h] > tmp) {
                    nums[l] = nums[h];
                    break;
                } else {
                    h--;
                }
            }
            while (l < h) {
                if (nums[l] < tmp) {
                    nums[h] = nums[l];
                    break;
                } else {
                    l++;
                }
            }
        }
        nums[l] = tmp;
        if (l == k - 1) {
            return;
        }
        if (k - 1 > l) {
            find(nums, l + 1, end, k);
        } else {
            find(nums, start, l, k);
        }
    }

    public static  void print(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public static void main(String[] args) {
        int[] nums={3,2,1,5,6,4};
        System.out.println(findKthLargest(nums,2));
    }
}
